package com.acwing.partition9;

import java.io.*;
import java.util.Map;
import java.util.TreeMap;

/**
 * @author `RKC`
 * @date 2021/12/4 9:49
 */
public class AC867分解质因数 {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        while (n-- > 0) {
            int x = Integer.parseInt(reader.readLine().split(" ")[0]);
            Map<Integer, Integer> prime = resolveToPrime(x);
            for (Map.Entry<Integer, Integer> entry : prime.entrySet()) {
                writer.write(entry.getKey() + " " + entry.getValue() + "\n");
            }
            writer.write("\n");
        }
        writer.flush();
    }

    private static Map<Integer, Integer> resolveToPrime(int x) {
        //key为质因子，value为质因子出现的次数
        Map<Integer, Integer> primesToCount = new TreeMap<>();
        for (int i = 2; i <= x / i; i++) {
            if (x % i == 0) {
                //i必定是质数因子
                int count = 0;
                while (x % i == 0) {
                    x /= i;
                    count++;
                }
                primesToCount.put(i, count);
            }
        }
        //大于sqrt(n)的数
        if (x > 1) primesToCount.put(x, 1);
        return primesToCount;
    }
}
